package leetcode20220116;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * https://leetcode-cn.com/problems/linked-list-random-node/submissions/
 * 优化，水塘抽样
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    List<Integer> list;
    Random random;

    public Solution(ListNode head) {
        list = new ArrayList<Integer>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        random = new Random();
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your Solution.java object will be instantiated and called as such:
 * Solution.java obj = new Solution.java(head);
 * int param_1 = obj.getRandom();
 */